
//456.123模式
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n=nums.size(),k=INT_MIN;  //k来记录栈中删除元素的最大值
        if(n<3) return false;
        stack<int> st({nums[n-1]});
        if(nums[n-2]>nums[n-1])  //将最后两个元素放入栈
        {
            k=max(k,st.top());
            st.pop();
        }
        st.push(nums[n-2]);


        for(int i=n-3;i>=0;i--)
        {
            if(nums[i]<k) return true;  //如果nums[i]<nums[k]一定存在满足条件的,因为栈中存在大于nums[k]的数据

            while(!st.empty()&&st.top()<nums[i])   //维护单调递减栈
            {
                k=max(k,st.top());
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};